Search results for "finite [mass]"

Measure and dimension functions: measurability and densities

1997

During the past several years, new types of geometric measure and dimension have been introduced; the packing measure and dimension, see [Su], [Tr] and [TT1]. These notions are playing an increasingly prevalent role in various aspects of dynamics and measure theory. Packing measure is a sort of dual of Hausdorff measure in that it is defined in terms of packings rather than coverings. However, in contrast to Hausdorff measure, the usual definition of packing measure requires two limiting procedures, first the construction of a premeasure and then a second standard limiting process to obtain the measure. This makes packing measure somewhat delicate to deal with. The question arises as to whe…

A note on the distance set problem in the plane

2001

We use a simple geometric-combinatorial argument to establish a quantitative relation between the generalized Hausdorff measure of a set and its distance set, extending a result originally due to Falconer.

Deciding reachability for planar multi-polynomial systems

1996

In this paper we investigate the decidability of the reachability problem for planar non-linear hybrid systems. A planar hybrid system has the property that its state space corresponds to the standard Euclidean plane, which is partitioned into a finite number of (polyhedral) regions. To each of these regions is assigned some vector field which governs the dynamical behaviour of the system within this region. We prove the decidability of point to point and region to region reachability problems for planar hybrid systems for the case when trajectories within the regions can be described by polynomials of arbitrary degree.

Quantum Finite Multitape Automata

1999

Quantum finite automata were introduced by C. Moore, J. P. Crutchfield [4], and by A. Kondacs and J. Watrous [3]. This notion is not a generalization of the deterministic finite automata. Moreover, in [3] it was proved that not all regular languages can be recognized by quantum finite automata. A. Ambainis and R. Freivalds [1] proved that for some languages quantum finite automata may be exponentially more concise rather than both deterministic and probabilistic finite automata. In this paper we introduce the notion of quantum finite multitape automata and prove that there is a language recognized by a quantum finite automaton but not by deterministic or probabilistic finite automata. This …

Probabilistic Reversible Automata and Quantum Automata

2002

To study relationship between quantum finite automata and probabilistic finite automata, we introduce a notion of probabilistic reversible automata (PRA, or doubly stochastic automata). We find that there is a strong relationship between different possible models of PRA and corresponding models of quantum finite automata. We also propose a classification of reversible finite 1-way automata.

Implications of quantum automata for contextuality

2014

We construct zero error quantum finite automata (QFAs) for promise problems which cannot be solved by bounded error probabilistic finite automata (PFAs). Here is a summary of our results: There is a promise problem solvable by an exact two way QFA in exponential expected time but not by any bounded error sublogarithmic space probabilistic Turing machine (PTM). There is a promise problem solvable by an exact two way QFA in quadratic expected time but not by any bounded error o(loglogn) space PTMs in polynomial expected time. The same problem can be solvable by a one way Las Vegas (or exact two way) QFA with quantum head in linear (expected) time. There is a promise problem solvable by a Las …

Amount of Nonconstructivity in Finite Automata

2009

When D. Hilbert used nonconstructive methods in his famous paper on invariants (1888), P.Gordan tried to prevent the publication of this paper considering these methods as non-mathematical. L. E. J. Brouwer in the early twentieth century initiated intuitionist movement in mathematics. His slogan was "nonconstructive arguments have no value for mathematics". However, P. Erdos got many exciting results in discrete mathematics by nonconstructive methods. It is widely believed that these results either cannot be proved by constructive methods or the proofs would have been prohibitively complicated. R.Freivalds [7] showed that nonconstructive methods in coding theory are related to the notion of…

A Uniform Way to Control Chief Series in Finite p -Groups and to Construct the Countable Algebraically Closed Locally Finite p -Groups

1986

Positive definite functions of finitary isometry groups over fields of odd characteristic

2007

Abstract This paper is part of a programme to describe the lattice of all two-sided ideals in complex group algebras of simple locally finite groups. Here we determine the extremal normalized positive definite functions for finitary groups of isometries, defined over fields of odd characteristic.

Einklassige Geschlechter totalpositiver quadratischer Formen in totalreellen algebraischen Zahlkörpern

1971

Abstract It is proved that totally positive quadratic forms with three or more variables and class number h = 1 exist only in a finite number of algebraic number fields. Each field allows only a finite number of such forms with bounded scale. To prove this, upper estimates for all local factors in Siegel's analytic formula are constructed by calculating explicitly numbers of solutions of quadratic congruences.